package com.yanceysong.codetop.s51_s60;


public class S59_Mid_151_翻转字符串里的单词 {

    /**
     * .S59_Mid_151_翻转字符串里的单词
     * .<p>
     * .LeetCode 链接：<a href="https://leetcode.cn/problems/reverse-words-in-a-string/">...</a>
     * .<p>
     * .=============================== 题目描述 ===============================
     * .给你一个字符串 s ，请你反转字符串中 "单词" 的顺序。
     * .- 单词：由非空格字符组成的一段连续字符。
     * .- 单词之间至少由一个空格分隔，可能存在前导、尾随以及多个连续空格。
     * .返回一个字符串，使得：
     * .1. 单词顺序颠倒（原第1个单词变为最后一个，依次类推）
     * .2. 单词之间只保留一个空格
     * .3. 结果中没有前导或尾随空格
     * .<p>
     * .示例：
     * .输入："  hello   world  " → 输出："world hello"
     * .输入："a good   example" → 输出："example good a"
     * .输入："  Bob    Loves  Alice  " → 输出："Alice Loves Bob"
     * .输入："    " → 输出："" (全空格 → 空字符串)
     * .<p>
     * .=============================== 核心标签 ===============================
     * .字符串 / 双指针 / 原地处理 / 清理空格 / 逆序遍历 / 模拟
     * .<p>
     * .=============================== 关键洞察 ===============================
     * .1. 结果只与“单词内容与顺序”相关，原来的多余空格都要被清理。
     * .2. 逆序扫描 + 收集单词 比 “split 后再逆序” 更节省空间（O(1) 额外，不算输出）。
     * .3. 用双指针从右向左找出每一个单词区间，加入结果构造；跳过多余空格。
     * .<p>
     * .=============================== 多种解法对比 ===============================
     * .1. 简单 split 法：trim + split(" ") + 过滤空串 + 逆序拼接 → 代码简单；但会生成中间数组 O(n) 空间。
     * .2. 双指针逆向法（推荐）：从末尾向前，跳过空格，锁定单词右端，再向左收集字符。空间 O(1)。
     * .3. 原地字符数组操作（再反转 + 清理空格）：更适合需要修改原数组场景，这里直接返回字符串即可用法2。
     * .<p>
     * .=============================== 双指针逆向法 ASCII 过程示例 ===============================
     * .s = "  a  good   example  "
     * .索引:  0 1 2 3 4 5 6 7 8 9 ...
     * .扫描：从末尾 i 往左：
     * .1) 跳过尾随空格 → i 指向 'e' (example 的最后一个字母)
     * .2) j = i，继续向左直到遇到空格，单词区间 [start=j..end=i]
     * .3) 添加 example → 结果："example"
     * .4) 继续跳过单词前的若干空格 → i 到 'd'
     * .5) 找到 "good" → 结果："example good"
     * .6) 找到 "a" → 结果："example good a"
     * .<p>
     * .=============================== 复杂度分析 ===============================
     * .n = s.length
     * .- 时间：O(n)（每个字符最多访问两次）
     * .- 空间：O(1) 额外（结果 StringBuilder 不计入原地额外空间）
     * .split 法则：时间 O(n)，空间 O(n)（数组与临时字符串）
     * .<p>
     * .=============================== 边界与特殊情况 ===============================
     * .1. 全空格：返回 ""。
     * .2. 单词之间多个空格：压缩为一个。
     * .3. 前后多空格：去除。
     * .4. 单个单词：原样返回。
     * .5. 包含标点：标点视为单词一部分，不做特殊处理，如 "hello, world!" → "world! hello,"。
     * .<p>
     * .=============================== 测试策略 ===============================
     * .- 基本案例 / 前后空格 / 多重空格 / 单个单词 / 全空格 / 标点 / 数字 / 大量字符。
     * .<p>
     * .=============================== 总结 ===============================
     * .推荐双指针逆向法：无需额外分割数组，逻辑清晰，空间低；split 法保留作易读版本。
     * <p>
     * .方法一：简洁版（基于 split）。
     * .步骤：trim 去前后空格 → split(" ") → 过滤空串 → 逆序拼接。
     * .劣势：split 生成中间数组占 O(n) 空间；多余空格会产生空串需要过滤。
     */
    public String reverseWordsSplit(String inputStr) {
        if (inputStr == null) return "";
        // 删除首尾空格后按单个空格分割（连续空格会产生空字符串）
        String[] rawParts = inputStr.trim().split(" ");
        StringBuilder resultBuilder = new StringBuilder();
        for (int idx = rawParts.length - 1; idx >= 0; idx--) {
            if (rawParts[idx].isEmpty()) { // 可能是由于多个空格导致的空串
                continue;
            }
            resultBuilder.append(rawParts[idx]).append(' ');
        }
        // 删除最后一个多余空格
        return resultBuilder.toString().trim();
    }

    /**
     * .方法二：双指针逆向扫描（推荐）。
     * .空间 O(1)（不计输出），时间 O(n)。
     * .思路：
     * .1. 从末尾开始，跳过空格找到单词末尾 end。
     * .2. 向左继续走到单词开头 start（遇到空格或走到 -1）。
     * .3. 把 [start+1, end] 这个单词加入结果。
     * .4. 重复直到扫描结束。
     */
    public String reverseWords(String inputStr) {
        if (inputStr == null) return "";
        // 原字符串长度
        int length = inputStr.length();
        StringBuilder resultBuilder = new StringBuilder();
        // 从末尾开始扫描的指针（用于向左跳过空格/提取单词）
        int scanIndex = length - 1;
        while (scanIndex >= 0) {
            // 1. 跳过末尾或当前段落的连续空格
            while (scanIndex >= 0 && inputStr.charAt(scanIndex) == ' ') {
                scanIndex--;
            }
            // 都是空格，结束
            if (scanIndex < 0) break;
            // 记录当前单词的最后一个字符位置
            int wordEnd = scanIndex;
            // 2. 继续向左，直到遇到空格或到达字符串最左端，定位单词起始的前一个位置
            while (scanIndex >= 0 && inputStr.charAt(scanIndex) != ' ') {
                scanIndex--;
            }
            // scanIndex 此时指向空格（或 -1），真实单词起点是 scanIndex + 1
            int wordStart = scanIndex;
            // 3. 追加当前找到的单词（区间 (wordStart, wordEnd]）到结果
            resultBuilder.append(inputStr, wordStart + 1, wordEnd + 1).append(' ');
            // 4. 继续循环，scanIndex 已经在单词左侧的空格上或者为 -1
        }
        // 去掉末尾多出的一个空格（如果有）
        if (!resultBuilder.isEmpty()) {
            resultBuilder.setLength(resultBuilder.length() - 1);
        }
        return resultBuilder.toString();
    }

    // ======================== 测试辅助方法 ========================

    private static void runTest(String input, String expected) {
        S59_Mid_151_翻转字符串里的单词 solver = new S59_Mid_151_翻转字符串里的单词();
        String outSplit = solver.reverseWordsSplit(input);
        String outTwoPtr = solver.reverseWords(input);
        System.out.println("输入: [" + input + "]");
        System.out.println("split法输出     : [" + outSplit + "]");
        System.out.println("双指针逆向输出  : [" + outTwoPtr + "]");
        System.out.println("期望            : [" + expected + "]");
        assert outSplit.equals(expected) : "split法结果不匹配";
        assert outTwoPtr.equals(expected) : "双指针法结果不匹配";
        System.out.println("✓ 测试通过\n");
    }

    // 构造一个大字符串用于性能测试（可选）
    private static String buildLargeInput(int words, int wordLen) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words; i++) {
            for (int j = 0; j < wordLen; j++) {
                sb.append((char) ('a' + (j % 26)));
            }
            if (i % 3 == 0) {
                sb.append("   "); // 插入多个空格
            } else {
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("=== 翻转字符串里的单词 测试开始 ===\n");

        // 基本示例
        runTest("  hello   world  ", "world hello");
        runTest("a good   example", "example good a");
        runTest("  Bob    Loves  Alice  ", "Alice Loves Bob");
        runTest("Alice", "Alice"); // 单个单词
        runTest("    ", ""); // 全空格
        runTest("  space before", "before space");
        runTest("ends with space   ", "space with ends");
        runTest("mix  of  multiple   spaces", "spaces multiple of mix");

        // 标点与数字
        runTest("  hello,   world! 123   ", "123 world! hello,");

        // 中文混合（视作普通字符）
        runTest("  我 爱  编程  ", "编程 爱 我");

        // 性能 / 较大输入（只验证不抛异常且两种实现一致）
        String largeInput = buildLargeInput(2000, 8); // 2000 个单词
        S59_Mid_151_翻转字符串里的单词 solver = new S59_Mid_151_翻转字符串里的单词();
        String largeA = solver.reverseWordsSplit(largeInput);
        String largeB = solver.reverseWords(largeInput);
        assert largeA.equals(largeB) : "大规模输入两种实现结果不一致";
        System.out.println("[大规模输入] 两种实现输出一致，长度=" + largeA.length());

        System.out.println("\n=== 所有测试完成 ===");
    }
}
